<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 5.2</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 5.2" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 5.2" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-5.xhtml#Chapter-5" rel="prev" title="Chapter 5" />
<link href="5_002e3.xhtml#g_t5_002e3" rel="next" title="5.3" />
<link href="5_002e1.xhtml#g_t5_002e1_002e5" rel="prev" title="5.1.5" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t5_002e2"></a>
<nav class="header">
<p>
Next: <a href="5_002e3.xhtml#g_t5_002e3" accesskey="n" rel="next">5.3</a>, Prev: <a href="5_002e1.xhtml#g_t5_002e1" accesskey="p" rel="prev">5.1</a>, Up: <a href="Chapter-5.xhtml#Chapter-5" accesskey="u" rel="prev">Chapter 5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="A-Register_002dMachine-Simulator"></a>
<h3 class="section"><span class="secnum">5.2</span><span class="sectitle">A Register-Machine Simulator</span></h3>

<p>In order to gain a good understanding of the design of register machines, we
must test the machines we design to see if they perform as expected.  One way
to test a design is to hand-simulate the operation of the controller, as in
<a href="5_002e1.xhtml#Exercise-5_002e5">Exercise 5.5</a>.  But this is extremely tedious for all but the simplest
machines.  In this section we construct a simulator for machines described in
the register-machine language.  The simulator is a Scheme program with four
interface procedures.  The first uses a description of a register machine to
construct a model of the machine (a data structure whose parts correspond to
the parts of the machine to be simulated), and the other three allow us to
simulate the machine by manipulating the model:
</p>
<blockquote>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">make-machine ⟨</span><var><span class="pln">register-names</span></var><span class="pln">⟩
              ⟨</span><var><span class="pln">operations</span></var><span class="pln">⟩
              ⟨</span><var><span class="pln">controller</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>constructs and returns a model of the machine with the given registers,
operations, and controller.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-register-contents! ⟨</span><var><span class="pln">machine-model</span></var><span class="pln">⟩ 
                        ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩ 
                        ⟨</span><var><span class="pln">value</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>stores a value in a simulated register in the given machine.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">get-register-contents ⟨</span><var><span class="pln">machine-model</span></var><span class="pln">⟩
                       ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>returns the contents of a simulated register in the given machine.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">start ⟨</span><var><span class="pln">machine-model</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>simulates the execution of the given machine, starting from the beginning of
the controller sequence and stopping when it reaches the end of the sequence.
</p></blockquote>

<p>As an example of how these procedures are used, we can define
<code>gcd-machine</code> to be a model of the <abbr>GCD</abbr> machine of 
<a href="5_002e1.xhtml#g_t5_002e1_002e1">5.1.1</a> as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> gcd-machine
  </span><span class="opn">(</span><span class="pln">make-machine
   </span><span class="lit">'</span><span class="opn">(</span><span class="pln">a b t</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'rem</span><span class="pln"> remainder</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">=</span><span class="pln"> </span><span class="pun">=</span><span class="clo">))</span><span class="pln">
   </span><span class="lit">'</span><span class="opn">(</span><span class="pln">test-b
       </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label gcd-done</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label test-b</span><span class="clo">))</span><span class="pln">
     gcd-done</span><span class="clo">)))</span></pre></div>

<p>The first argument to <code>make-machine</code> is a list of register names.  The
next argument is a table (a list of two-element lists) that pairs each
operation name with a Scheme procedure that implements the operation (that is,
produces the same output value given the same input values).  The last argument
specifies the controller as a list of labels and machine instructions, as in
<a href="5_002e1.xhtml#g_t5_002e1">5.1</a>.
</p>
<p>To compute <abbr>GCD</abbr>s with this machine, we set the input registers, start
the machine, and examine the result when the simulation terminates:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-register-contents! gcd-machine </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">206</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">done</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">set-register-contents! gcd-machine </span><span class="lit">'b</span><span class="pln"> </span><span class="lit">40</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">done</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">start gcd-machine</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">done</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">get-register-contents gcd-machine </span><span class="lit">'a</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">2</span></i>
</pre></div>

<p>This computation will run much more slowly than a <code>gcd</code> procedure written
in Scheme, because we will simulate low-level machine instructions, such as
<code>assign</code>, by much more complex operations.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e7"></a>Exercise 5.7:</strong> Use the simulator to test the
machines you designed in <a href="5_002e1.xhtml#Exercise-5_002e4">Exercise 5.4</a>.
</p></blockquote>


<a id="g_t5_002e2_002e1"></a>
<a id="The-Machine-Model"></a>
<h4 class="subsection"><span class="secnum">5.2.1</span><span class="sectitle">The Machine Model</span></h4>

<p>The machine model generated by <code>make-machine</code> is represented as a
procedure with local state using the message-passing techniques developed in
<a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>.  To build this model, <code>make-machine</code> begins by calling
the procedure <code>make-new-machine</code> to construct the parts of the machine
model that are common to all register machines.  This basic machine model
constructed by <code>make-new-machine</code> is essentially a container for some
registers and a stack, together with an execution mechanism that processes the
controller instructions one by one.
</p>
<p><code>Make-machine</code> then extends this basic model (by sending it messages) to
include the registers, operations, and controller of the particular machine
being defined.  First it allocates a register in the new machine for each of
the supplied register names and installs the designated operations in the
machine.  Then it uses an <a id="index-assembler"></a>
<em>assembler</em> (described below in 
<a href="#g_t5_002e2_002e2">5.2.2</a>) to transform the controller list into instructions for the new
machine and installs these as the machine’s instruction sequence.
<code>Make-machine</code> returns as its value the modified machine model.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-machine register-names 
                      ops 
                      controller-text</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">machine </span><span class="opn">(</span><span class="pln">make-new-machine</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">for-each </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">register-name</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">((</span><span class="pln">machine </span><span class="lit">'allocate-register</span><span class="clo">)</span><span class="pln"> 
                 register-name</span><span class="clo">))</span><span class="pln">
              register-names</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">machine </span><span class="lit">'install-operations</span><span class="clo">)</span><span class="pln"> ops</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">machine </span><span class="lit">'install-instruction-sequence</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">assemble controller-text machine</span><span class="clo">))</span><span class="pln">
    machine</span><span class="clo">))</span></pre></div>

<a id="Registers"></a>
<h5 class="subsubheading">Registers</h5>

<p>We will represent a register as a procedure with local state, as in
<a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>.  The procedure <code>make-register</code> creates a register that
holds a value that can be accessed or changed:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-register name</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">contents </span><span class="lit">'</span><span class="pun">*</span><span class="pln">unassigned</span><span class="pun">*</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch message</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'get</span><span class="clo">)</span><span class="pln"> contents</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'set</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">value</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> contents value</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
             </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                     REGISTER"</span><span class="pln">
                    message</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>The following procedures are used to access registers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-contents register</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">register </span><span class="lit">'get</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-contents! register value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">register </span><span class="lit">'set</span><span class="clo">)</span><span class="pln"> value</span><span class="clo">))</span></pre></div>

<a id="The-stack"></a>
<h5 class="subsubheading">The stack</h5>

<p>We can also represent a stack as a procedure with local state.  The procedure
<code>make-stack</code> creates a stack whose local state consists of a list of the
items on the stack.  A stack accepts requests to <code>push</code> an item onto the
stack, to <code>pop</code> the top item off the stack and return it, and to
<code>initialize</code> the stack to empty.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-stack</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">s </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">push x</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> s </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x s</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pop</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? s</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Empty stack: POP"</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">top </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> s </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s</span><span class="clo">))</span><span class="pln">
            top</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">initialize</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> s </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
      </span><span class="lit">'done</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch message</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'push</span><span class="clo">)</span><span class="pln"> push</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'pop</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pop</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'initialize</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">initialize</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
             </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: STACK"</span><span class="pln">
                    message</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>The following procedures are used to access stacks:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pop stack</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stack </span><span class="lit">'pop</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">push stack value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">stack </span><span class="lit">'push</span><span class="clo">)</span><span class="pln"> value</span><span class="clo">))</span></pre></div>

<a id="The-basic-machine"></a>
<h5 class="subsubheading">The basic machine</h5>

<p>The <code>make-new-machine</code> procedure, shown in <a href="#Figure-5_002e13">Figure 5.13<!-- /@w --></a>, 
constructs
an object whose local state consists of a stack, an initially empty instruction
sequence, a list of operations that initially contains an operation to
initialize the stack, and a <a id="index-register-table"></a>
<em>register table</em> that initially contains
two registers, named <code>flag</code> and <code>pc</code> (for “program counter”).  The
internal procedure <code>allocate-register</code> adds new entries to the register
table, and the internal procedure <code>lookup-register</code> looks up registers in
the table.
</p>
<p><strong><a id="Figure-5_002e13"></a>Figure 5.13:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> The <code>make-new-machine</code>
procedure, which implements the basic machine model.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-new-machine</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">pc </span><span class="opn">(</span><span class="pln">make-register </span><span class="lit">'pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">flag </span><span class="opn">(</span><span class="pln">make-register </span><span class="lit">'flag</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">stack </span><span class="opn">(</span><span class="pln">make-stack</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">the-instruction-sequence </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">the-ops
           </span><span class="opn">(</span><span class="pln">list 
            </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'initialize-stack</span><span class="pln">
                  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
                    </span><span class="opn">(</span><span class="pln">stack </span><span class="lit">'initialize</span><span class="clo">)))))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">register-table
           </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'pc</span><span class="pln"> pc</span><span class="clo">)</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'flag</span><span class="pln"> flag</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">allocate-register name</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assoc name register-table</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="err">error</span><span class="pln"> 
             </span><span class="str">"Multiply defined register: "</span><span class="pln"> 
             name</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> register-table
                  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
                   </span><span class="opn">(</span><span class="pln">list name 
                         </span><span class="opn">(</span><span class="pln">make-register name</span><span class="clo">))</span><span class="pln">
                   register-table</span><span class="clo">)))</span><span class="pln">
        </span><span class="lit">'register-allocated</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup-register name</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">val 
               </span><span class="opn">(</span><span class="pln">assoc name register-table</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> val
              </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> val</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown register:"</span><span class="pln"> 
                     name</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">execute</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">insts </span><span class="opn">(</span><span class="pln">get-contents pc</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? insts</span><span class="clo">)</span><span class="pln">
              </span><span class="lit">'done</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln">
                </span><span class="opn">((</span><span class="pln">instruction-execution-proc 
                  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> insts</span><span class="clo">)))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">execute</span><span class="clo">)))))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch message</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'start</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">set-contents! 
                pc
                the-instruction-sequence</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">execute</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> 
                message 
                </span><span class="lit">'install-instruction-sequence</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">seq</span><span class="clo">)</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> 
                  the-instruction-sequence 
                  seq</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message 
                    </span><span class="lit">'allocate-register</span><span class="clo">)</span><span class="pln"> 
               allocate-register</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'get-register</span><span class="clo">)</span><span class="pln"> 
               lookup-register</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message 
                    </span><span class="lit">'install-operations</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">ops</span><span class="clo">)</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> the-ops 
                       </span><span class="opn">(</span><span class="pln">append the-ops ops</span><span class="clo">))))</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'stack</span><span class="clo">)</span><span class="pln"> stack</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'operations</span><span class="clo">)</span><span class="pln"> 
               the-ops</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                            MACHINE"</span><span class="pln">
                           message</span><span class="clo">))))</span><span class="pln">
      dispatch</span><span class="clo">)))</span></pre></div>

<p>The <code>flag</code> register is used to control branching in the simulated machine.
<code>Test</code> instructions set the contents of <code>flag</code> to the result of the
test (true or false).  <code>Branch</code> instructions decide whether or not to
branch by examining the contents of <code>flag</code>.
</p>
<p>The <code>pc</code> register determines the sequencing of instructions as the machine
runs.  This sequencing is implemented by the internal procedure <code>execute</code>.
In the simulation model, each machine instruction is a data structure that
includes a procedure of no arguments, called the <a id="index-instruction-execution-procedure"></a>
<em>instruction execution procedure</em>, 
such that calling this procedure simulates executing the
instruction.  As the simulation runs, <code>pc</code> points to the place in the
instruction sequence beginning with the next instruction to be executed.
<code>Execute</code> gets that instruction, executes it by calling the instruction
execution procedure, and repeats this cycle until there are no more
instructions to execute (i.e., until <code>pc</code> points to the end of the
instruction sequence).
</p>
<p>As part of its operation, each instruction execution procedure modifies
<code>pc</code> to indicate the next instruction to be executed.  <code>Branch</code> and
<code>goto</code> instructions change <code>pc</code> to point to the new destination.  All
other instructions simply advance <code>pc</code>, making it point to the next
instruction in the sequence.  Observe that each call to <code>execute</code> calls
<code>execute</code> again, but this does not produce an infinite loop because
running the instruction execution procedure changes the contents of <code>pc</code>.
</p>
<p><code>Make-new-machine</code> returns a <code>dispatch</code> procedure that implements
message-passing access to the internal state.  Notice that starting the machine
is accomplished by setting <code>pc</code> to the beginning of the instruction
sequence and calling <code>execute</code>.
</p>
<p>For convenience, we provide an alternate procedural interface to a machine’s
<code>start</code> operation, as well as procedures to set and examine register
contents, as specified at the beginning of <a href="#g_t5_002e2">5.2</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">start machine</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">machine </span><span class="lit">'start</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-register-contents 
         machine register-name</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">get-contents 
   </span><span class="opn">(</span><span class="pln">get-register machine register-name</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-register-contents! 
         machine register-name value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-contents! 
   </span><span class="opn">(</span><span class="pln">get-register machine register-name</span><span class="clo">)</span><span class="pln"> 
   value</span><span class="clo">)</span><span class="pln">
  </span><span class="lit">'done</span><span class="clo">)</span></pre></div>

<p>These procedures (and many procedures in <a href="#g_t5_002e2_002e2">5.2.2</a> and <a href="#g_t5_002e2_002e3">5.2.3</a>)
use the following to look up the register with a given name in a given machine:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-register machine reg-name</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">machine </span><span class="lit">'get-register</span><span class="clo">)</span><span class="pln"> reg-name</span><span class="clo">))</span></pre></div>

<a id="g_t5_002e2_002e2"></a>
<a id="The-Assembler"></a>
<h4 class="subsection"><span class="secnum">5.2.2</span><span class="sectitle">The Assembler</span></h4>

<p>The assembler transforms the sequence of controller expressions for a machine
into a corresponding list of machine instructions, each with its execution
procedure.  Overall, the assembler is much like the evaluators we studied in
<a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>—there is an input language (in this case, the
register-machine language) and we must perform an appropriate action for each
type of expression in the language.
</p>
<p>The technique of producing an execution procedure for each instruction is just
what we used in <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a> to speed up the evaluator by separating
analysis from runtime execution.  As we saw in <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>, much useful
analysis of Scheme expressions could be performed without knowing the actual
values of variables.  Here, analogously, much useful analysis of
register-machine-language expressions can be performed without knowing the
actual contents of machine registers.  For example, we can replace references
to registers by pointers to the register objects, and we can replace references
to labels by pointers to the place in the instruction sequence that the label
designates.
</p>
<p>Before it can generate the instruction execution procedures, the assembler must
know what all the labels refer to, so it begins by scanning the controller text
to separate the labels from the instructions.  As it scans the text, it
constructs both a list of instructions and a table that associates each label
with a pointer into that list.  Then the assembler augments the instruction
list by inserting the execution procedure for each instruction.
</p>
<p>The <code>assemble</code> procedure is the main entry to the assembler.  It takes the
controller text and the machine model as arguments and returns the instruction
sequence to be stored in the model.  <code>Assemble</code> calls
<code>extract-labels</code> to build the initial instruction list and label table
from the supplied controller text.  The second argument to
<code>extract-labels</code> is a procedure to be called to process these results:
This procedure uses <code>update-insts!</code> to generate the instruction execution
procedures and insert them into the instruction list, and returns the modified
list.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assemble controller-text machine</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">extract-labels controller-text
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">insts labels</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">update-insts! insts labels machine</span><span class="clo">)</span><span class="pln">
      insts</span><span class="clo">)))</span></pre></div>

<p><code>Extract-labels</code> takes as arguments a list <code>text</code> (the sequence of
controller instruction expressions) and a <code>receive</code> procedure.
<code>Receive</code> will be called with two values: (1) a list <code>insts</code> of
instruction data structures, each containing an instruction from <code>text</code>;
and (2) a table called <code>labels</code>, which associates each label from
<code>text</code> with the position in the list <code>insts</code> that the label
designates.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extract-labels text receive</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? text</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">receive </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">extract-labels 
       </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> text</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">insts labels</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">next-inst </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> text</span><span class="clo">)))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? next-inst</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">receive 
                   insts
                   </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
                    </span><span class="opn">(</span><span class="pln">make-label-entry 
                     next-inst
                     insts</span><span class="clo">)</span><span class="pln">
                    labels</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">receive 
                   </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-instruction 
                          next-inst</span><span class="clo">)</span><span class="pln">
                         insts</span><span class="clo">)</span><span class="pln">
                   labels</span><span class="clo">)))))))</span></pre></div>

<p><code>Extract-labels</code> works by sequentially scanning the elements of the
<code>text</code> and accumulating the <code>insts</code> and the <code>labels</code>.  If an
element is a symbol (and thus a label) an appropriate entry is added to the
<code>labels</code> table.  Otherwise the element is accumulated onto the
<code>insts</code> list.<a class="footnote_link" id="DOCF289" href="#FOOT289"><sup>289</sup></a>
</p>
<p><code>Update-insts!</code> modifies the instruction list, which initially contains
only the text of the instructions, to include the corresponding execution
procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">update-insts! insts labels machine</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">pc </span><span class="opn">(</span><span class="pln">get-register machine </span><span class="lit">'pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">flag </span><span class="opn">(</span><span class="pln">get-register machine </span><span class="lit">'flag</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">stack </span><span class="opn">(</span><span class="pln">machine </span><span class="lit">'stack</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">ops </span><span class="opn">(</span><span class="pln">machine </span><span class="lit">'operations</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">for-each
     </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">inst</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">set-instruction-execution-proc!
        inst
        </span><span class="opn">(</span><span class="pln">make-execution-procedure
         </span><span class="opn">(</span><span class="pln">instruction-text inst</span><span class="clo">)</span><span class="pln"> 
         labels
         machine
         pc
         flag
         stack
         ops</span><span class="clo">)))</span><span class="pln">
     insts</span><span class="clo">)))</span></pre></div>

<p>The machine instruction data structure simply pairs the instruction text with
the corresponding execution procedure.  The execution procedure is not yet
available when <code>extract-labels</code> constructs the instruction, and is
inserted later by <code>update-insts!</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-instruction text</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> text </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">instruction-text inst</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">instruction-execution-proc inst</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> inst</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-instruction-execution-proc!
         inst
         proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-cdr! inst proc</span><span class="clo">))</span></pre></div>

<p>The instruction text is not used by our simulator, but it is handy to keep
around for debugging (see <a href="#Exercise-5_002e16">Exercise 5.16</a>).
</p>
<p>Elements of the label table are pairs:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-label-entry label-name insts</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> label-name insts</span><span class="clo">))</span></pre></div>

<p>Entries will be looked up in the table with
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup-label labels label-name</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">val </span><span class="opn">(</span><span class="pln">assoc label-name labels</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> val
        </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> val</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Undefined label: ASSEMBLE"</span><span class="pln"> 
               label-name</span><span class="clo">))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-5_002e8"></a>Exercise 5.8:</strong> The following register-machine code
is ambiguous, because the label <code>here</code> is defined more than once:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">start
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label here</span><span class="clo">))</span><span class="pln">
here
  </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">const </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label there</span><span class="clo">))</span><span class="pln">
here
  </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">const </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label there</span><span class="clo">))</span><span class="pln">
there</span></pre></div>

<p>With the simulator as written, what will the contents of register <code>a</code> be
when control reaches <code>there</code>?  Modify the <code>extract-labels</code> procedure
so that the assembler will signal an error if the same label name is used to
indicate two different locations.
</p></blockquote>

<a id="g_t5_002e2_002e3"></a>
<a id="Generating-Execution-Procedures-for-Instructions"></a>
<h4 class="subsection"><span class="secnum">5.2.3</span><span class="sectitle">Generating Execution Procedures for Instructions</span></h4>

<p>The assembler calls <code>make-execution-procedure</code> to generate the execution
procedure for an instruction.  Like the <code>analyze</code> procedure in the
evaluator of <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a>, this dispatches on the type of instruction to
generate the appropriate execution procedure.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-execution-procedure 
         inst labels machine pc flag stack ops</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'assign</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-assign 
          inst machine labels ops pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'test</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-test 
          inst machine labels ops flag pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'branch</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-branch 
          inst machine labels flag pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'goto</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-goto inst machine labels pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'save</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-save inst machine stack pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'restore</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-restore inst machine stack pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> inst</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'perform</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-perform
          inst machine labels ops pc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown instruction 
                      type: ASSEMBLE"</span><span class="pln">
                     inst</span><span class="clo">))))</span></pre></div>

<p>For each type of instruction in the register-machine language, there is a
generator that builds an appropriate execution procedure.  The details of these
procedures determine both the syntax and meaning of the individual instructions
in the register-machine language.  We use data abstraction to isolate the
detailed syntax of register-machine expressions from the general execution
mechanism, as we did for evaluators in <a href="4_002e1.xhtml#g_t4_002e1_002e2">4.1.2</a>, by using syntax
procedures to extract and classify the parts of an instruction.
</p>
<a id="Assign-instructions"></a>
<h5 class="subsubheading"><code>Assign</code> instructions</h5>

<p>The <code>make-assign</code> procedure handles <code>assign</code> instructions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-assign 
         inst machine labels operations pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">target 
         </span><span class="opn">(</span><span class="pln">get-register 
          machine 
          </span><span class="opn">(</span><span class="pln">assign-reg-name inst</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">value-exp </span><span class="opn">(</span><span class="pln">assign-value-exp inst</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">value-proc
           </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operation-exp? value-exp</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">make-operation-exp
                value-exp 
                machine
                labels
                operations</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">make-primitive-exp
                </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> value-exp</span><span class="clo">)</span><span class="pln">
                machine
                labels</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; execution procedure</span></span><span class="pln">
                   </span><span class="roman"><span class="com">; for </span><code><span class="com">assign</span></code></span><span class="pln">
        </span><span class="opn">(</span><span class="pln">set-contents! target </span><span class="opn">(</span><span class="pln">value-proc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">)))))</span></pre></div>

<p><code>Make-assign</code> extracts the target register name (the second element of the
instruction) and the value expression (the rest of the list that forms the
instruction) from the <code>assign</code> instruction using the selectors
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assign-reg-name assign-instruction</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> assign-instruction</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assign-value-exp assign-instruction</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cddr</span><span class="pln"> assign-instruction</span><span class="clo">))</span></pre></div>

<p>The register name is looked up with <code>get-register</code> to produce the target
register object.  The value expression is passed to <code>make-operation-exp</code>
if the value is the result of an operation, and to <code>make-primitive-exp</code>
otherwise.  These procedures (shown below) parse the value expression and
produce an execution procedure for the value.  This is a procedure of no
arguments, called <code>value-proc</code>, which will be evaluated during the
simulation to produce the actual value to be assigned to the register.  Notice
that the work of looking up the register name and parsing the value expression
is performed just once, at assembly time, not every time the instruction is
simulated.  This saving of work is the reason we use execution procedures, and
corresponds directly to the saving in work we obtained by separating program
analysis from execution in the evaluator of <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a>.
</p>
<p>The result returned by <code>make-assign</code> is the execution procedure for the
<code>assign</code> instruction.  When this procedure is called (by the machine
model’s <code>execute</code> procedure), it sets the contents of the target register
to the result obtained by executing <code>value-proc</code>.  Then it advances the
<code>pc</code> to the next instruction by running the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-contents! pc </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-contents pc</span><span class="clo">))))</span></pre></div>

<p><code>Advance-pc</code> is the normal termination for all instructions except
<code>branch</code> and <code>goto</code>.
</p>
<a id="Test_002c-branch_002c-and-goto-instructions"></a>
<h5 class="subsubheading"><code>Test</code>, <code>branch</code>, and <code>goto</code> instructions</h5>

<p><code>Make-test</code> handles <code>test</code> instructions in a similar way.  It
extracts the expression that specifies the condition to be tested and generates
an execution procedure for it.  At simulation time, the procedure for the
condition is called, the result is assigned to the <code>flag</code> register, and
the <code>pc</code> is advanced:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">make-test 
   inst machine labels operations flag pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">condition </span><span class="opn">(</span><span class="pln">test-condition inst</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operation-exp? condition</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">condition-proc
               </span><span class="opn">(</span><span class="pln">make-operation-exp
                condition 
                machine
                labels
                operations</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">set-contents! 
             flag </span><span class="opn">(</span><span class="pln">condition-proc</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Bad TEST instruction: 
                ASSEMBLE"</span><span class="pln"> inst</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">test-condition test-instruction</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> test-instruction</span><span class="clo">))</span></pre></div>

<p>The execution procedure for a <code>branch</code> instruction checks the contents of
the <code>flag</code> register and either sets the contents of the <code>pc</code> to the
branch destination (if the branch is taken) or else just advances the <code>pc</code>
(if the branch is not taken).  Notice that the indicated destination in a
<code>branch</code> instruction must be a label, and the <code>make-branch</code> procedure
enforces this.  Notice also that the label is looked up at assembly time, not
each time the <code>branch</code> instruction is simulated.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">make-branch 
   inst machine labels flag pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">dest </span><span class="opn">(</span><span class="pln">branch-dest inst</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">label-exp? dest</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">insts
               </span><span class="opn">(</span><span class="pln">lookup-label 
                labels 
                </span><span class="opn">(</span><span class="pln">label-exp-label dest</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-contents flag</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">set-contents! pc insts</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Bad BRANCH instruction: 
                ASSEMBLE"</span><span class="pln">
               inst</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">branch-dest branch-instruction</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> branch-instruction</span><span class="clo">))</span></pre></div>

<p>A <code>goto</code> instruction is similar to a branch, except that the destination
may be specified either as a label or as a register, and there is no condition
to check—the <code>pc</code> is always set to the new destination.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-goto inst machine labels pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">dest </span><span class="opn">(</span><span class="pln">goto-dest inst</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">label-exp? dest</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">insts
                  </span><span class="opn">(</span><span class="pln">lookup-label 
                   labels
                   </span><span class="opn">(</span><span class="pln">label-exp-label dest</span><span class="clo">))))</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">set-contents! pc insts</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">register-exp? dest</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">reg
                  </span><span class="opn">(</span><span class="pln">get-register 
                   machine
                   </span><span class="opn">(</span><span class="pln">register-exp-reg dest</span><span class="clo">))))</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">set-contents! 
                pc
                </span><span class="opn">(</span><span class="pln">get-contents reg</span><span class="clo">)))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Bad GOTO instruction: 
                        ASSEMBLE"</span><span class="pln">
                       inst</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">goto-dest goto-instruction</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> goto-instruction</span><span class="clo">))</span></pre></div>

<a id="Other-instructions"></a>
<h5 class="subsubheading">Other instructions</h5>

<p>The stack instructions <code>save</code> and <code>restore</code> simply use the stack with
the designated register and advance the <code>pc</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-save inst machine stack pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">reg </span><span class="opn">(</span><span class="pln">get-register 
              machine
              </span><span class="opn">(</span><span class="pln">stack-inst-reg-name inst</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">push stack </span><span class="opn">(</span><span class="pln">get-contents reg</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-restore inst machine stack pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">reg </span><span class="opn">(</span><span class="pln">get-register
              machine
              </span><span class="opn">(</span><span class="pln">stack-inst-reg-name inst</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">set-contents! reg </span><span class="opn">(</span><span class="pln">pop stack</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stack-inst-reg-name 
         stack-instruction</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> stack-instruction</span><span class="clo">))</span></pre></div>

<p>The final instruction type, handled by <code>make-perform</code>, generates an
execution procedure for the action to be performed.  At simulation time, the
action procedure is executed and the <code>pc</code> advanced.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-perform 
         inst machine labels operations pc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">action </span><span class="opn">(</span><span class="pln">perform-action inst</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operation-exp? action</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">action-proc
               </span><span class="opn">(</span><span class="pln">make-operation-exp
                action
                machine
                labels
                operations</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">action-proc</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">advance-pc pc</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Bad PERFORM instruction: 
                ASSEMBLE"</span><span class="pln">
               inst</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">perform-action inst</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> inst</span><span class="clo">))</span></pre></div>

<a id="Execution-procedures-for-subexpressions"></a>
<h5 class="subsubheading">Execution procedures for subexpressions</h5>

<p>The value of a <code>reg</code>, <code>label</code>, or <code>const</code> expression may be
needed for assignment to a register (<code>make-assign</code>) or for input to an
operation (<code>make-operation-exp</code>, below).  The following procedure
generates execution procedures to produce values for these expressions during
the simulation:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-primitive-exp exp machine labels</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">constant-exp? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">c </span><span class="opn">(</span><span class="pln">constant-exp-value exp</span><span class="clo">)))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> c</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">label-exp? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">insts
                </span><span class="opn">(</span><span class="pln">lookup-label 
                 labels
                 </span><span class="opn">(</span><span class="pln">label-exp-label exp</span><span class="clo">))))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> insts</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">register-exp? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">r </span><span class="opn">(</span><span class="pln">get-register
                   machine
                   </span><span class="opn">(</span><span class="pln">register-exp-reg exp</span><span class="clo">))))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-contents r</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown expression type: 
                      ASSEMBLE"</span><span class="pln">
                     exp</span><span class="clo">))))</span></pre></div>

<p>The syntax of <code>reg</code>, <code>label</code>, and <code>const</code> expressions is
determined by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">register-exp? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'reg</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">register-exp-reg exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">constant-exp? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'const</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">constant-exp-value exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">label-exp? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'label</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">label-exp-label exp</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span></pre></div>

<p><code>Assign</code>, <code>perform</code>, and <code>test</code> instructions may include the
application of a machine operation (specified by an <code>op</code> expression) to
some operands (specified by <code>reg</code> and <code>const</code> expressions).  The
following procedure produces an execution procedure for an “operation
expression”—a list containing the operation and operand expressions from the
instruction:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-operation-exp
         exp machine labels operations</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">op </span><span class="opn">(</span><span class="pln">lookup-prim 
             </span><span class="opn">(</span><span class="pln">operation-exp-op exp</span><span class="clo">)</span><span class="pln">
             operations</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">aprocs
         </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">e</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">make-primitive-exp 
                 e machine labels</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">operation-exp-operands exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply op </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p</span><span class="clo">))</span><span class="pln">
                              aprocs</span><span class="clo">)))))</span></pre></div>

<p>The syntax of operation expressions is determined by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operation-exp? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">tagged-list? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'op</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operation-exp-op operation-exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> operation-exp</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operation-exp-operands operation-exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> operation-exp</span><span class="clo">))</span></pre></div>

<p>Observe that the treatment of operation expressions is very much like the
treatment of procedure applications by the <code>analyze-application</code> procedure
in the evaluator of <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a> in that we generate an execution
procedure for each operand.  At simulation time, we call the operand procedures
and apply the Scheme procedure that simulates the operation to the resulting
values.  The simulation procedure is found by looking up the operation name in
the operation table for the machine:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup-prim symbol operations</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">val </span><span class="opn">(</span><span class="pln">assoc symbol operations</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> val
        </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> val</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown operation: ASSEMBLE"</span><span class="pln">
               symbol</span><span class="clo">))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-5_002e9"></a>Exercise 5.9:</strong> The treatment of machine operations
above permits them to operate on labels as well as on constants and the
contents of registers.  Modify the expression-processing procedures to enforce
the condition that operations can be used only with registers and constants.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e10"></a>Exercise 5.10:</strong> Design a new syntax for
register-machine instructions and modify the simulator to use your new syntax.
Can you implement your new syntax without changing any part of the simulator
except the syntax procedures in this section?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e11"></a>Exercise 5.11:</strong> When we introduced <code>save</code>
and <code>restore</code> in <a href="5_002e1.xhtml#g_t5_002e1_002e4">5.1.4</a>, we didn’t specify what would happen
if you tried to restore a register that was not the last one saved, as in the
sequence
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">save y</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">save x</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">restore y</span><span class="clo">)</span></pre></div>

<p>There are several reasonable possibilities for the meaning of <code>restore</code>:
</p>
<ol>
<li> <code>(restore y)</code> puts into <code>y</code> the last value saved on the stack,
regardless of what register that value came from.  This is the way our
simulator behaves.  Show how to take advantage of this behavior to eliminate
one instruction from the Fibonacci machine of <a href="5_002e1.xhtml#g_t5_002e1_002e4">5.1.4</a> (<a href="5_002e1.xhtml#Figure-5_002e12">Figure 5.12</a>).

</li><li> <code>(restore y)</code> puts into <code>y</code> the last value saved on the stack, but
only if that value was saved from <code>y</code>; otherwise, it signals an error.
Modify the simulator to behave this way.  You will have to change <code>save</code>
to put the register name on the stack along with the value.

</li><li> <code>(restore y)</code> puts into <code>y</code> the last value saved from <code>y</code>
regardless of what other registers were saved after <code>y</code> and not restored.
Modify the simulator to behave this way.  You will have to associate a separate
stack with each register.  You should make the <code>initialize-stack</code>
operation initialize all the register stacks.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e12"></a>Exercise 5.12:</strong> The simulator can be used to help
determine the data paths required for implementing a machine with a given
controller.  Extend the assembler to store the following information in the
machine model:
</p>
<ul>
<li> a list of all instructions, with duplicates removed, sorted by instruction type
(<code>assign</code>, <code>goto</code>, and so on);

</li><li> a list (without duplicates) of the registers used to hold entry points (these
are the registers referenced by <code>goto</code> instructions);

</li><li> a list (without duplicates) of the registers that are <code>save</code>d
or <code>restore</code>d;

</li><li> for each register, a list (without duplicates) of the sources from which it is
assigned (for example, the sources for register <code>val</code> in the factorial
machine of <a href="5_002e1.xhtml#Figure-5_002e11">Figure 5.11</a> are <code>(const 1)</code> and <code>((op *) (reg n)
(reg val))</code>).

</li></ul>

<p>Extend the message-passing interface to the machine to provide access to this
new information.  To test your analyzer, define the Fibonacci machine from
<a href="5_002e1.xhtml#Figure-5_002e12">Figure 5.12</a> and examine the lists you constructed.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e13"></a>Exercise 5.13:</strong> Modify the simulator so that it
uses the controller sequence to determine what registers the machine has rather
than requiring a list of registers as an argument to <code>make-machine</code>.
Instead of pre-allocating the registers in <code>make-machine</code>, you can
allocate them one at a time when they are first seen during assembly of the
instructions.
</p></blockquote>

<a id="g_t5_002e2_002e4"></a>
<a id="Monitoring-Machine-Performance"></a>
<h4 class="subsection"><span class="secnum">5.2.4</span><span class="sectitle">Monitoring Machine Performance</span></h4>

<p>Simulation is useful not only for verifying the correctness of a proposed
machine design but also for measuring the machine’s performance.  For example,
we can install in our simulation program a “meter” that measures the number
of stack operations used in a computation.  To do this, we modify our simulated
stack to keep track of the number of times registers are saved on the stack and
the maximum depth reached by the stack, and add a message to the stack’s
interface that prints the statistics, as shown below.  We also add an operation
to the basic machine model to print the stack statistics, by initializing
<code>the-ops</code> in <code>make-new-machine</code> to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'initialize-stack</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">stack </span><span class="lit">'initialize</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'print-stack-statistics</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">stack </span><span class="lit">'print-statistics</span><span class="clo">))))</span></pre></div>

<p>Here is the new version of <code>make-stack</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-stack</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">s </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">number-pushes </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">max-depth </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">current-depth </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">push x</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> s </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x s</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> number-pushes </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> number-pushes</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> current-depth </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> current-depth</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> max-depth 
            </span><span class="opn">(</span><span class="pln">max current-depth max-depth</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pop</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? s</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Empty stack: POP"</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">top </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> s </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> current-depth
                  </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> current-depth </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
            top</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">initialize</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> s </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> number-pushes </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> max-depth </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> current-depth </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'done</span><span class="clo">)</span><span class="pln">

    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">print-statistics</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">display </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'total-pushes</span><span class="pln"> 
                     </span><span class="lit">'</span><span class="pun">=</span><span class="pln"> 
                     number-pushes
                     </span><span class="lit">'maximum-depth</span><span class="pln">
                     </span><span class="lit">'</span><span class="pun">=</span><span class="pln">
                     max-depth</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch message</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'push</span><span class="clo">)</span><span class="pln"> push</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'pop</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pop</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'initialize</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">initialize</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> message </span><span class="lit">'print-statistics</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">print-statistics</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
             </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: STACK"</span><span class="pln">
                    message</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p><a href="#Exercise-5_002e15">Exercise 5.15</a> through <a href="#Exercise-5_002e19">Exercise 5.19</a> describe other useful
monitoring and debugging features that can be added to the register-machine
simulator.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e14"></a>Exercise 5.14:</strong> Measure the number of pushes and
the maximum stack depth required to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> for various small values of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> using the factorial machine shown in <a href="5_002e1.xhtml#Figure-5_002e11">Figure 5.11</a>.  From your data
determine formulas in terms of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> for the total number of push operations
and the maximum stack depth used in computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> for any <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>&gt;</mo>
    <mn>1</mn>
  </mrow>
</math>. Note
that each of these is a linear function of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and is thus determined by two
constants.  In order to get the statistics printed, you will have to augment
the factorial machine with instructions to initialize the stack and print the
statistics.  You may want to also modify the machine so that it repeatedly
reads a value for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, computes the factorial, and prints the result (as we
did for the <abbr>GCD</abbr> machine in <a href="5_002e1.xhtml#Figure-5_002e4">Figure 5.4</a>), so that you will not
have to repeatedly invoke <code>get-register-contents</code>,
<code>set-register-contents!</code>, and <code>start</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e15"></a>Exercise 5.15:</strong> Add <a id="index-instruction-counting"></a>
<em>instruction counting</em> 
to the register machine simulation.  That is, have the machine model
keep track of the number of instructions executed.  Extend the machine model’s
interface to accept a new message that prints the value of the instruction
count and resets the count to zero.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e16"></a>Exercise 5.16:</strong> Augment the simulator to provide
for <a id="index-instruction-tracing"></a>
<em>instruction tracing</em>.  That is, before each instruction is
executed, the simulator should print the text of the instruction.  Make the
machine model accept <code>trace-on</code> and <code>trace-off</code> messages to turn
tracing on and off.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e17"></a>Exercise 5.17:</strong> Extend the instruction tracing of
<a href="#Exercise-5_002e16">Exercise 5.16</a> so that before printing an instruction, the simulator
prints any labels that immediately precede that instruction in the controller
sequence.  Be careful to do this in a way that does not interfere with
instruction counting (<a href="#Exercise-5_002e15">Exercise 5.15</a>).  You will have to make the
simulator retain the necessary label information.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e18"></a>Exercise 5.18:</strong> Modify the <code>make-register</code>
procedure of <a href="#g_t5_002e2_002e1">5.2.1</a> so that registers can be traced.  Registers
should accept messages that turn tracing on and off.  When a register is
traced, assigning a value to the register should print the name of the
register, the old contents of the register, and the new contents being
assigned.  Extend the interface to the machine model to permit you to turn
tracing on and off for designated machine registers.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e19"></a>Exercise 5.19:</strong> Alyssa P. Hacker wants a
<a id="index-breakpoint"></a>
<em>breakpoint</em> feature in the simulator to help her debug her machine
designs.  You have been hired to install this feature for her.  She wants to be
able to specify a place in the controller sequence where the simulator will
stop and allow her to examine the state of the machine.  You are to implement a
procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-breakpoint ⟨</span><var><span class="pln">machine</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">label</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">n</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>that sets a breakpoint just before the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> instruction after the given
label.  For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-breakpoint gcd-machine </span><span class="lit">'test-b</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></pre></div>

<p>installs a breakpoint in <code>gcd-machine</code> just before the assignment to
register <code>a</code>.  When the simulator reaches the breakpoint it should print
the label and the offset of the breakpoint and stop executing instructions.
Alyssa can then use <code>get-register-contents</code> and
<code>set-register-contents!</code> to manipulate the state of the simulated machine.
She should then be able to continue execution by saying
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">proceed-machine ⟨</span><var><span class="pln">machine</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>She should also be able to remove a specific breakpoint by means of
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">cancel-breakpoint ⟨</span><var><span class="pln">machine</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">label</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">n</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>or to remove all breakpoints by means of
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">cancel-all-breakpoints ⟨</span><var><span class="pln">machine</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>
</blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT289"><p><a class="footnote_backlink" href="#DOCF289"><sup>289</sup></a>
Using the <code>receive</code> procedure here is a way to
get <code>extract-labels</code> to effectively return two values—<code>labels</code> and
<code>insts</code>—without explicitly making a compound data structure to hold
them.  An alternative implementation, which returns an explicit pair of values,
is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extract-labels text</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? text</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">result 
             </span><span class="opn">(</span><span class="pln">extract-labels </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> text</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">insts </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> result</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">labels </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> result</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">next-inst </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> text</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? next-inst</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
                 insts
                 </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">make-label-entry 
                   next-inst insts</span><span class="clo">)</span><span class="pln"> 
                  labels</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">make-instruction next-inst</span><span class="clo">)</span><span class="pln"> 
                  insts</span><span class="clo">)</span><span class="pln">
                 labels</span><span class="clo">)))))))</span></pre></div>

<p>which would be called by <code>assemble</code> as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assemble controller-text machine</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">result 
         </span><span class="opn">(</span><span class="pln">extract-labels controller-text</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">insts </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> result</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">labels </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> result</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">update-insts! insts labels machine</span><span class="clo">)</span><span class="pln">
      insts</span><span class="clo">)))</span></pre></div>

<p>You can consider our use of <code>receive</code> as demonstrating an elegant way to
return multiple values, or simply an excuse to show off a programming trick.
An argument like <code>receive</code> that is the next procedure to be invoked is
called a “continuation.”  Recall that we also used continuations to implement
the backtracking control structure in the <code>amb</code> evaluator in 
<a href="4_002e3.xhtml#g_t4_002e3_002e3">4.3.3</a>.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="5_002e3.xhtml#g_t5_002e3" accesskey="n" rel="next">5.3</a>, Prev: <a href="5_002e1.xhtml#g_t5_002e1" accesskey="p" rel="prev">5.1</a>, Up: <a href="#g_t5_002e2" accesskey="u" rel="prev">5.2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>